package com.itheima.leetcode;

import java.util.HashMap;

/**
 * LFU 缓存 - 双指针(最不经常使用（LFU）)
 */
public class LFULeetcode460 {

    public static void main(String[] args) {
        // cnt(x) = 键 x 的使用计数
        // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
        LFUCache lfu = new LFUCache(2);
        lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
        lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        lfu.get(1);      // 返回 1
        // cache=[1,2], cnt(2)=1, cnt(1)=2
        lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        // cache=[3,1], cnt(3)=1, cnt(1)=2
        lfu.get(2);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        // cache=[3,1], cnt(3)=2, cnt(1)=2
        lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        // cache=[4,3], cnt(4)=1, cnt(3)=2
        lfu.get(1);      // 返回 -1（未找到）
        lfu.get(3);      // 返回 3
        // cache=[3,4], cnt(4)=1, cnt(3)=3
        lfu.get(4);      // 返回 4
        // cache=[3,4], cnt(4)=2, cnt(3)=3
    }

    static class LFUCache {

        static class Node {
            Node prev;
            Node next;
            int key;
            int value;
            int freq = 1; // 频率

            public Node() {
            }

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        static class DoublyLinkedList {
            Node head;
            Node tail;
            int size;

            public DoublyLinkedList() { // 哨兵节点
                head = tail = new Node();
                head.next = tail;
                tail.prev = head;
            }

            // 头部添加     head<->1<->2<->tail
            public void addFrist(Node newFirst) { // O(1)
                Node oldFirst = head.next;
                newFirst.prev = head;
                newFirst.next = oldFirst;
                head.next = newFirst;
                oldFirst.prev = newFirst;
                size++;
            }

            // 已知节点删除
            public void remove(Node node) { // O(1)
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
                size--;
            }

            // 尾部删除
            public Node removeLast() { // O(1)
                Node last = tail.prev;
                remove(last);
                return last;
            }

            public boolean isEmpty() {
                return 0 == size;
            }
        }

        private HashMap<Integer, Node> kvMap = new HashMap<>();
        private HashMap<Integer, DoublyLinkedList> freqMap = new HashMap<>();
        private int capacity;
        private int minFreq = 1; // 最小频率

        public LFUCache(int capacity) {
            this.capacity = capacity;
        }

        /*
            key 不存在
                返回  -1
            key 存在
                返回  value 值
                增加节点的使用频度，将其转移到频度+1的链表当中
         */
        public int get(int key) {
            if (!kvMap.containsKey(key)) {
                return -1;
            }
            Node node = kvMap.get(key);
            freqMap.get(node.freq).remove(node);
            if (freqMap.get(node.freq).isEmpty() && minFreq == node.freq) {
                minFreq++;
            }
            node.freq++;
            /*DoublyLinkedList list = freqMap.get(node.freq);
            if (null == list) {
                list = new DoublyLinkedList();
                freqMap.put(node.freq, list);
            }
            list.addFrist(node);*/
            freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
                    .addFrist(node);
            return node.value;
        }

        public void put(int key, int value) {
            if (kvMap.containsKey(key)) { // 更新
                Node node = kvMap.get(key);
                freqMap.get(node.freq).remove(node);
                if (freqMap.get(node.freq).isEmpty() && minFreq == node.freq) {
                    minFreq++;
                }
                node.freq++;
                freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
                        .addFrist(node);
                node.value = value;
            } else { // 新增
                if (capacity == kvMap.size()) {
                    Node node = freqMap.get(minFreq).removeLast();
                    kvMap.remove(node.key);
                }
                Node node = new Node(key, value);
                kvMap.put(key, node);
                freqMap.computeIfAbsent(1, k -> new DoublyLinkedList())
                        .addFrist(node);
                minFreq = 1;
            }
        }
    }
}
